//01背包问题
#include<bits/stdc++.h>
using namespace std;
int main()
{
	cout<<"capacity:";
	int V;
	while(cin>>V)
	{
		cout<<"object num:";
		int n;
		cin>>n;
		int *w=new int[n+1];//n个物体的价值
		int *v=new int[n+1];//n个物体的大小
		v[0]=0;
		w[0]=0;
		cout<<"object size:";
		for(int i=1;i<=n;i++)cin>>v[i];
		cout<<"object value:";
		for(int i=1;i<=n;i++)cin>>w[i];
		int **F=new int*[n+1];
		for(int i=0;i<=n;i++)
		{
			F[i]=new int[V+1];
			if(i==0)
			{
				for(int j=0;j<=V;j++)F[i][j]=0;
			}
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=0;j<=V;j++)
			{
				//背包当前容量是否能容纳下当前i号物体
				if(v[i]>j)
				{
					//容纳不下则为前号物体同个状态
					F[i][j]=F[i-1][j];
				}
				else
				{
					//容纳得下进行比较
					F[i][j]=(F[i-1][j]>(F[i-1][j-v[i]]+w[i]))?F[i-1][j]:(F[i-1][j-v[i]]+w[i]);
				}
			}
		}
		cout<<"max value:"<<F[n][V]<<endl;
		cout<<"capacity:";
	}
}